home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / HULL.ARJ / HULL.C next >
C/C++ Source or Header  |  1992-07-15  |  4KB  |  155 lines
  1. /*  Copyright (c) 1992, by John Johnson
  2.  
  3.     If you find this code useful, interesting or inspiring, I would
  4.     like to hear from you, contact me on D.W.'s Toolbox (404) 471-6636
  5.  
  6.     Compiled using QuickC v2.5.
  7.  
  8.     The following code was written based on algorithms in the book
  9.     'Algorithms' by Robert Sedgewick.
  10. */
  11.  
  12. #include <math.h>
  13. #include <graph.h>
  14. #include <float.h>
  15. #include <stdlib.h>
  16.  
  17. struct POINT
  18. {   float x;
  19.     float y;
  20. };
  21.  
  22. //
  23. //  Passed two POINTs, returns a number between 0 and 360 that is
  24. //  NOT the angle made by p1 & p2 with the horizontal but which
  25. //  has the same order properties as that angle.
  26. //
  27. float theta(struct POINT p1, struct POINT p2)
  28. {   float dx, dy, ax, ay;
  29.     float t;
  30.  
  31.     dx = p2.x - p1.x;   ax = fabs(dx);
  32.     dy = p2.y - p1.y;   ay = fabs(dy);
  33.     if (dx == 0 && dy == 0)
  34.         t = 0;
  35.     else
  36.         t = dy / (ax + ay);
  37.     if (dx < 0)
  38.         t = 2 - t;
  39.     else
  40.         if (dy < 0)
  41.             t = 4 + t;
  42.     return t * 90.0;
  43. }
  44.  
  45. //
  46. //  Function wrap taken from `Algorithms' pg. 364
  47. //
  48. //  Given a set of POINTs, orders the points to produce
  49. //  a convex hull about the points. The first n points in the
  50. //  array are rearranged to generate this hull,
  51. //  and the number of points (n) on the hull is returned.
  52. //
  53.  
  54. int wrap(struct POINT p[], int N)
  55. {   int i, min, M;
  56.     float minangle, v;
  57.     struct POINT t;
  58.  
  59.     min = 0;
  60.     for(i = 1; i < N; i++)
  61.         if (p[i].y < p[min].y) min = i;
  62.     M = -1;
  63.     p[N] = p[min];
  64.     minangle = 0.0;
  65.     do
  66.     {   M++;
  67.         t = p[M];
  68.         p[M] = p[min];
  69.         p[min] = t;
  70.         min = N;
  71.         v = minangle;
  72.         minangle = 360.0;
  73.         for(i = M+1; i < N; i++)
  74.             if (theta(p[M], p[i]) > v)
  75.                 if (theta(p[M], p[i]) < minangle)
  76.                 {   min = i; minangle = theta(p[M], p[min]); }
  77.     } while (min < N);
  78.     return M;
  79. }
  80.  
  81. //
  82. //  Test above algorithms.
  83. //
  84. main(int argc, char *argv[])
  85. {   struct POINT testarray[] =
  86.     {   {3, 9},                    // point A, Test set pg. 349
  87.         {11, 1},
  88.         {6, 8},
  89.         {4, 3},
  90.         {5, 15},
  91.         {8, 11},
  92.         {1, 6},
  93.         {7, 4},
  94.         {9, 7},
  95.         {14, 5},
  96.         {10, 13},
  97.         {16, 14},
  98.         {15, 2},
  99.         {13, 16},
  100.         {3, 12},
  101.         {12, 10},                   // point P
  102.         {0, 0}                      // scratch space
  103.     };
  104.     int i,
  105.         arraysize,
  106.         pointsonhull;
  107.     float scalex = 10.0,
  108.           scaley = 12.8,
  109.           minx,
  110.           miny,
  111.           maxx,
  112.           maxy;
  113.     struct videoconfig vconfig;
  114.  
  115.     arraysize = sizeof(testarray)/sizeof(testarray[0])-1;
  116.     pointsonhull = wrap(testarray, arraysize);
  117.     printf("Points on hull %d\n", pointsonhull);
  118.     minx = FLT_MAX;
  119.     maxx = FLT_MIN;
  120.     miny = FLT_MAX;
  121.     minx = FLT_MIN;
  122.     for(i = 0; i <= arraysize; i++)
  123.     {   printf("Point %2d: %2.1f %2.1f\n", i, testarray[i].x, testarray[i].y);
  124.         // compute scaling values for x & y.
  125.         minx = min(minx, testarray[i].x);
  126.         maxx = max(maxx, testarray[i].x);
  127.         miny = min(miny, testarray[i].y);
  128.         maxy = max(maxy, testarray[i].y);
  129.     }
  130.     i = getch();
  131.     if (_setvideomode(_MAXRESMODE) == 0)
  132.     {   printf("initialize video to max res. failed\n");
  133.         exit(1);
  134.     }
  135.     _getvideoconfig(&vconfig);
  136.  
  137.     scalex = (vconfig.numxpixels*.9) / (maxx - minx);
  138.     scaley = (vconfig.numypixels*.9/1.28) / (maxy - miny) * 1.28;
  139.     if (vconfig.bitsperpixel>1)
  140.         _setcolor(3);
  141.     else
  142.         _setcolor(1);
  143.     for(i = 0; i <= arraysize; i++)
  144.         _setpixel((short)(testarray[i].x*scalex), (short)(testarray[i].y*scaley));
  145.     i = getch();
  146.     if (vconfig.bitsperpixel>1)
  147.         _setcolor(2);
  148.     _moveto((short)(testarray[0].x*scalex), (short)(testarray[0].y*scaley));
  149.     for(i = 1; i <= pointsonhull; i++)
  150.         _lineto((short)(testarray[i].x*scalex), (short)(testarray[i].y*scaley));
  151.     _lineto((short)(testarray[0].x*scalex), (short)(testarray[0].y*scaley));
  152.     i = getch();
  153.     _setvideomode(_DEFAULTMODE);
  154. }
  155.